package 中等.树;


import util.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。
 * 请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：
 * mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
 * maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。
 * 返回数组 answer 。
 *
 * @ https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/description/?envType=daily-question&envId=2024-02-24
 * @date 2024/02/27
 */
public class 二叉搜索树最近节点查询_2476 {

    public static void main(String[] args) {

    }

    /**
     * 在二叉搜索树上面二分查找（超时！！！）
     * 二叉搜索树可能不是平衡的，如果是链式的，复杂度较高
     */
    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {

        List<List<Integer>> lists = new ArrayList<>();

        for (Integer val : queries) {

            List<Integer> list = new ArrayList<>();

            list.add(findMax(root, val));
            list.add(findMin(root, val));

            lists.add(list);

        }

        return lists;
    }

    private Integer findMin(TreeNode node, Integer val) {
        int ans = -1;
        TreeNode tempNode = node;
        while (tempNode != null) {
            if (tempNode.val >= val) {
                ans = tempNode.val;
                tempNode = tempNode.left;
            } else {
                tempNode = tempNode.right;
            }
        }
        return ans;
    }

    private Integer findMax(TreeNode node, Integer val) {
        int ans = -1;
        TreeNode tempNode = node;
        while (tempNode != null) {
            if (tempNode.val <= val) {
                ans = tempNode.val;
                tempNode = tempNode.right;
            } else {
                tempNode = tempNode.left;
            }
        }
        return ans;
    }

}
